package leetcode.leetcode518;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/10
 */
public class Leetcode518 {

    public int coinChange(int[] coins, int amount) {
        return rec(coins.length-1, coins, amount);
    }

    /**
     * @param index 当前处理的金额面值
     * @param coins 金额数组
     * @param remainder 剩余的金额
     * @return 解的个数
     */
    public int rec(int index, int[] coins, int remainder) {
        // 情况1:剩余金额<0
        // 情况2:剩余金额>0
        // 情况3:剩余金额==0
        if (remainder == 0) {
            return 1;
        } else if (remainder < 0) {
            return 0;
        } else {
            int count = 0;
            for (int i = index; i >= 0; i--) {
                count += rec(i, coins, remainder - coins[i]);
            }
            return count;
        }
    }
}
